##
# \file cantor.py
#

# --  Python imports  --
from math import floor, sqrt
# -- End Python imports --

# --  Pybrain imports  --
# -- End Pybrain imports --

# --  Project imports  --
# -- End Project imports --

##
# \class Cantor
# \details The Cantor pairing function is a pairing function.
# http://en.wikipedia.org/wiki/Cantor_pairing_function
class Cantor:

    ##
    # \brief Returns the Cantor pair of the two numbers k1, and k2.
    # \details The Cantor Pairing function is defined as: \n
    # \f$ \pi(k_{1}, k_{2}) := \frac{1}{2}(k_{1} + k_{2})(k_{1} + k_{2} + 1) + k_{2} \f$
    # \pre none
    # \post none
    # \param k1 A number in the range 0 to X.
    # \param k2 A number in the range 0 to Y.
    # \return The Cantor pairing of k1 and k2.
    @staticmethod
    def pair(k1, k2):
        return ( ((k1 + k2) * (k1 + k2 + 1) / 2) + k2  )

    ##
    # \brief Separates a Cantor pair into two values k1, and k2.
    # \details Inverting the Cantor Pairing function requires the following 4 steps: \n
    # 1. \f$ w = \lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor \f$ \n
    # 2. \f$ t = \frac{w^{2} + w}{2} \f$ \n
    # 3. \f$ y = z - t \f$ \n
    # 4. \f$ x = w - y \f$
    # \pre none
    # \post none
    # \param z A number assumed to be a Cantor pair.
    # \return Tuple of two numbers (k1, k2) that when Cantor paired produce the input parameter.
    @staticmethod
    def inv(z):
        w = floor( (sqrt(8 * z + 1) - 1) / 2 )
        t = (w * w + w) / 2
        y = z - t
        x = w - y
        return (x, y)

    ##
    # \details Performs the Cantor pairing function over a set of elements.
    # \pre none
    # \post none
    # \param set A list of elements to pair into a single number.
    # \return A number representing the paired numbers.
    @staticmethod
    def pairN(set):
        # Pair the first two elements
        p = Cantor.pair(set[0], set[1])
        for i in range(2, len(set)):
            # Continue the pairing process one element at a time
            p = Cantor.pair(p, set[i])
        return p

    ##
    # \details Separates a set of Cantor pairs into a set of elements.
    # \pre none
    # \post none
    # \param ps A single number representing multiple Cantor pairs.
    # \param n The number of pairs that ps is made of, and therefore should be split into.
    # \return A set of numbers representing the original set of numbers.
    @staticmethod
    def invN(ps, n):
        zs = []
        # Invert the initial number into the first pair of k1, and k2
        zs.extend(Cantor.inv(ps))
        while len(zs) < n:
            # Invert the first element into k1, and k2
            x  = list(Cantor.inv(zs[0]))
            # Remove the element we inverted into k1, and k2
            del zs[0]
            # Insert the new k1/k2 pair to the head of the list so
            # we can repeat the process.
            zs = x + zs
        return zs
